package advance.x000.acw_91;


import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。
 * <p>
 * Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
 * <p>
 * 输入格式
 * 第一行输入整数 n。
 * <p>
 * 接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。
 * <p>
 * 对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。
 * <p>
 * 输出格式
 * 输出一个整数，表示最短 Hamilton 路径的长度。
 * <p>
 * 数据范围
 * 1≤n≤20  # 20！ 非常大=>剪支优化，是否被遍历过，只保留最优解
 * 0≤a[i,j]≤107
 * 输入样例：
 * 5
 * 0 2 4 5 1
 * 2 0 6 5 3
 * 4 6 0 8 3
 * 5 5 8 0 5
 * 1 3 3 5 0
 * 输出样例：
 * 18
 */
public class Main {
    /**
     * 哈密顿路径——旅行商问题
     * np完全问题-- 无法在多项式时间内算出来
     * 1.哪些点被用过
     * 2.最后停在哪个点上
     * 3.时间复杂度： 2 ^ 20 * 20 = 2*10^7=2000w
     * f[state][j] =min{ f[state_k][k]+weight[k][j]} state_k=state 除掉j之后的集合
     * state：20位整数
     * state:哪些点被用过，到达j点
     */

    public static void main(String[] args) {
        Main solution = new Main();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] weight = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                weight[i][j] = scanner.nextInt();
            }
        }
        long ans = solution.hamilton(n, weight);
        System.out.println(ans);
    }


    int hamilton(int n, int[][] weight) {
        // f[state][目前在第j点]
        int[][] f = new int[1 << n][n + 1];
        for (int i = 0; i < 1 << n; i++) {
            // 动归初始值置无穷大
            Arrays.fill(f[i], Integer.MAX_VALUE / 2);
        }
        f[1][0] = 0; // 第0个点
        // 从1(000001)开始[第0个点]出发
        for (int i = 1; i < 1 << n; i++) {
            // 遍历1-20个点
            for (int j = 0; j < n; j++) {
                // state[j]==1 刚刚经过j点 state第j个bit一定是1
                if (((i >> j) & 1) == 1) {
                    for (int k = 0; k < n; k++) {
                        // 遍历所有i -> j 可能经过k点并计算所有可能性
                        // state xor (1<<j) => 将state[j]置0 => 上一课被经历过的点的j位应该为0
                        if ((((i ^ 1 << j) >> k) & 1) == 1) {
                            f[i][j] = Math.min(f[i ^ 1 << j][k] + weight[k][j], f[i][j]);
                        }

                    }
                }
            }
        }
        return f[1 << n - 1][n - 1];
    }
}
